/*
题目: 单词替换
在英语中，我们有一个叫做 词根(root) 的概念，可以词根后面添加其他一些词组成另一个较长的单词——我们称这个词为 继承词(successor)。例如，词根an，跟随着单词 other(其他)，可以形成新的单词 another(另一个)。

现在，给定一个由许多词根组成的词典 dictionary 和一个用空格分隔单词形成的句子 sentence。你需要将句子中的所有继承词用词根替换掉。如果继承词有许多可以形成它的词根，则用最短的词根替换它。

你需要输出替换之后的句子。
https://leetcode.cn/problems/replace-words/
 */
public class ReplaceWords {
    public static class Trie {
        boolean isEnd = false; // 前缀到此结束
        Trie[] children = new Trie[26];
        public Trie() { }
    }
    Trie root = null;

    public String replaceWords(List<String> dictionary, String sentence) {
        // 使用字典树, 记录所有词根
        root = new Trie();
        // 预处理所有词根
        for (String str : dictionary) {
            int len = str.length();
            Trie head = root;

            for (int i = 0; i < len; i ++) {
                char ch = str.charAt(i);
                int pos = ch - 'a';
                // 这里通了, 也就是不是空指针了, 就表示有有元素
                if (head.children[pos] == null) { head.children[pos] = new Trie(); }

                head = head.children[pos];
            }
            head.isEnd = true;  // 最后一个地方 标记为 结束
        }

        StringBuilder builder = new StringBuilder();

        String[] subArray = sentence.split(" "); // 分割
        for (String sub : subArray) {
            // 开始搜索词根
            int len = sub.length();
            Trie head = root;

            boolean valid = false; // 有没有这个前缀
            for (int i = 0; i < len; i ++) {
                int pos = sub.charAt(i) - 'a';

                if (head.children[pos] == null) { // 没有这样的前缀, 此路不通
                    break;
                }
                // 找到了这样的前缀
                if (head.children[pos].isEnd) {
                    builder.append(sub.substring(0, i + 1));
                    valid = true; // 标记
                    break;
                }

                head = head.children[pos];
            }
            if (!valid) { builder.append(sub); } // 没有找到前缀就 原样放回
            builder.append(" ");
        }

        builder.deleteCharAt(builder.length() - 1);
        return builder.toString();
    }
}
